Pascal's Triangle

Jan 31, 2015 23:32
　I often solve some problems in the intervals between my study. Today, I chose a problem with Pascal's triangle from Project Euler. Pascal's triangle is a triangle that is created by the simple rules, such as following:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1

　And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal's triangle. The number of elements that I have to check is about 500 quadrillion (5 times 10 to the 17th power).

　I wrote a simple program code which calculates Pascal's triangle made of residue of 7 (modularized by 7?). However, this program took about 30 seconds to check 5 billion elements in my computer. This means it will take 95 years to solve this problem. I think there is a smart analytical solution because there are too many elements to solve using dynamic programming. I couldn't solve this problem today, but I like such a problem that remind me of the splendor of algorithms.
No. 1　Timmy's correction
  • I often solve some problems in the intervals between my study.
  • I often solve some problems (or: mathematical puzzles) in the intervals between my study (or: studies).
  • I couldn't solve this problem today, but I like such a problem that remind me of the splendor of algorithms.
  • I couldn't solve this problem today, but I like such problems that remind me of the splendor of algorithms.
Interesting!
kanotown
Thank you so much always for your correction! :D
Timmy
You are welcome!
No. 2　thethinker83's correction
  • Today, I chose a problem with Pascal's triangle from Project Euler.
  • This sentence is perfect! No correction needed!
  • Pascal's triangle is a triangle that is created by the simple rules, such as following:
  • Pascal's triangle is a triangle that is created by the simple rules, such as the following:
  • And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal's triangle.
  • And the problem demanded the number of entries which are not divisible by 7 in the first one billion rows of Pascal's triangle.
    　You can also use "asked for" instead of "demanded" here
  • The number of elements that I have to check is about 500 quadrillion (5 times 10 to the 17th power).
  • This sentence is perfect! No correction needed!
  • I wrote a simple program code which calculates Pascal's triangle made of residue of 7 (modularized by 7?).
  • I wrote a simple program code which calculates Pascal's triangle made of residue of 7 (modularized by 7?).
    　I would use "modularized by 7" or just "modulo 7".
  • However, this program took about 30 seconds to check 5 billion elements in my computer.
  • This sentence is perfect! No correction needed!
  • This means it will take 95 years to solve this problem.
  • This sentence is perfect! No correction needed!
  • I think there is a smart analytical solution because there are too many elements to solve using dynamic programming.
  • This sentence is perfect! No correction needed!
This was very interesting and very well written. I wish I had a better idea how to solve this problem.
kanotown
Thank you very much for correcting me! :)
Your comments were very encouraging for me. I will try to solve this problem during my free time. :D
BACK